package 算法.leetcode.labuladong.structure;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @author lchenglong
 * @date 2022/6/22
 */
public class LFUCache {
    // key 到 val 的映射
    HashMap<Integer,Integer> KV;
    // key 到 freq 的映射
    HashMap<Integer,Integer> KF;
    // freq 到 key 列表的映射，我们后文称为 FK 表
    HashMap<Integer, LinkedHashSet<Integer>> FK;
    int minFreq;
    int cap;
    public LFUCache(int capacity) {
        KV = new HashMap<>();
        KF = new HashMap<>();
        FK = new HashMap<>();
        this.minFreq = 0;
        this.cap = capacity;
    }

    public int get(int key) {
        // 不存在返回-1
        if (!KV.containsKey(key))return -1;
        // 增加Key对应的频率
        increaseFreq(key);
        return KV.get(key);
    }

    public void put(int key, int val) {
        // 容量小于0 则结束
        if (cap<=0) return;
        // 存在过则更新KV,增加freq
        if (KV.containsKey(key)){
            KV.put(key,val);
            increaseFreq(key);
            return;
        }
        // 如果超过容量,需要移除一个
        if (cap<=KV.size()){
            removeMinFreq(key);
        }

        // 增加KV
        KV.put(key,val);
        // KF增加freq
        KF.put(key,1);
        // FK更新freq集合
        FK.putIfAbsent(1,new LinkedHashSet<>());
        FK.get(1).add(key);
        this.minFreq = 1;

    }

    public void increaseFreq(int key){
        // freq+1
        int freq = KF.get(key);
        KF.put(key,freq+1);
        // FK表移除
        LinkedHashSet<Integer> freqSet = FK.get(freq);
        freqSet.remove(key);
        // FK表添加
        FK.putIfAbsent(freq+1,new LinkedHashSet<>());
        FK.get(freq+1).add(key);
        // 原freq集合如果不存在则移除,并修改最小频率
        if (freqSet.isEmpty()){
            FK.remove(freq);
            if (freq == minFreq){
                minFreq++;
            }
        }
    }

    public void removeMinFreq(int key){
        // 找出最小频率的Key集合
        LinkedHashSet<Integer> minFreqSet = FK.get(this.minFreq);
        // FK集合移除
        Integer removeKey = minFreqSet.iterator().next();
        minFreqSet.remove(removeKey);
        if (minFreqSet.isEmpty()){
            FK.remove(this.minFreq);
        }
        // KV 集合移除
        KV.remove(key);
        // KF 集合移除
        KF.remove(key);
    }
}
